package leetcode.editor.cn;

import java.util.Arrays;

/**
 * ******************************************************
 *
 * @author liugh9
 * @version 1.0
 * @classname HeadSort
 * @description
 * @date 2023/09/17 10:34
 * <p>
 * ******************************************************
 */
public class HeadSort {

    public static void main(String[] args) {
        int[] arr = {4, 2, 8, 0, 5, 7, 1, 3, 9};
        System.out.println("排序前:" + Arrays.toString(arr));
        sort0(arr);
        System.out.println("排序后:" + Arrays.toString(arr));
    }

    private static void heapSort(int[] arr) {
        int temp = 0;
        //堆排序
        for (int i = arr.length / 2 - 1; i >= 0; i--) {
            adjustHeap(arr, i, arr.length);
        }

        for (int j = arr.length - 1; j > 0; j--) {
            temp = arr[j];
            arr[j] = arr[0];
            arr[0] = temp;
            adjustHeap(arr, 0, j);
        }

        System.out.println("数组=" + Arrays.toString(arr));
    }

    /**
     * 将以i对应的非叶子节点的树调整成一个大顶堆
     * 举例 int[] arr = {4,6,8,5,9};=>i=1 =>{4,9,8,5,6} => i=0 =>{9,6,8,5,4}
     *
     * @param arr
     * @param i      表示非叶子节点在数组中的索引
     * @param length 对多少个元素进行调整
     */
    public static void adjustHeap(int[] arr, int i, int length) {
        //a[i]>a[2i+1]&&a[i]>a[2i+2]
        int temp = arr[i];
        for (int k = i * 2 + 1; k < length; k = k * 2 + 1) {
            //先比较左子节点和右子节点的大小，最大的那个和temp进行交换
            if (k + 1 < length && arr[k] < arr[k + 1]) {
                k++;//k指向右子节点
            }
            //如果非子节点的值小于左子节点和右子节点的值
            if (arr[k] > temp) {
                //temp和arr[k]进行交换
                arr[i] = arr[k];
                i = k;//继续循环比较，假设k是左子节点，k+1是右子节点，然后引出公式
            } else {
                break;
            }
        }
        //当for循环结束后，我们已经将以i为父节点的树的最大值，放在了最顶上（局部）
        arr[i] = temp;
    }



    /**
     * 下标0有数据
     *
     * @param nums
     */
    public static void sort0(int[] nums) {
        int n = nums.length - 1;
        // 调整初始化数据的位置（非叶子节点：因为非叶子节点不需要下沉）
        // 构成最大堆
        for (int k = n / 2 - 1; k >= 0; k--) {
            sink0(nums, k, n);
        }

        // 交互第一个和最后一个值，再下沉第一个值
        while (n > 0) {
            swap(nums, 0, n--);
            sink0(nums, 0, n);
        }
    }

    private static void sink0(int[] nums, int k, final int N) {
        while (2 * k + 1 <= N) {
            int j = 2 * k + 1;
            // 找到只有子节点最大的那个数值的下标
            if (j < N && less(nums, j, j + 1)) {
                j++;
            }
            // 如果当前节点比他的子节点都大，就结束
            if (!less(nums, k, j)) {
                break;
            }
            // 否则与最大子节点交互位置
            swap(nums, k, j);
            // 再判断交互后的位置需不需下沉
            k = j;
        }
    }

    /**
     * 下标0不能有数据
     *
     * @param nums
     */
    public static void sort1(int[] nums) {
        int n = nums.length - 1;
        // 调整初始化数据的位置（非叶子节点：因为非叶子节点不需要下沉）
        for (int k = n / 2; k >= 1; k--) {
            sink1(nums, k, n);
        }

        while (n > 1) {
            swap(nums, 1, n--);
            sink1(nums, 1, n);
        }
    }

    private static void sink1(int[] nums, int k, final int N) {
        while (2 * k <= N) {
            int j = 2 * k;
            if (j < N && less(nums, j, j + 1)) {
                j++;
            }
            if (!less(nums, k, j)) {
                break;
            }
            swap(nums, k, j);
            k = j;
        }
    }

    private static void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    private static boolean less(int[] nums, int i, int j) {
        return nums[i] < nums[j];
    }
}

